There exist a wide variety of potential applications for video at rates below 64 kilobits per second (kb/s), including videophones, multimedia e-mail, remote sensing and interactive multimedia databases, to name a few. To implement such applications, for example, over the Public Switched Telephone Network (PSTN), requires that bitrates be reduced to approximately 30 kb/s. The requirement of a very low bit rate, however, necessitates the use of compression algorithms which allow a significant amount of information to be transmitted over channels with low bandwidth.
Video compression algorithms typically compress data by relying on redundancy that is inherently present in video sequences. Such redundancy may occur both spatially and temporally. One technique of taking advantage of both the spatial and temporal redundancy is to use vector quantization. In vector quantization, a codebook of codewords is maintained, such that the codewords are representative of coding blocks in the video sequence. Representing a block of picture elements or pels in a frame by an address in the codebook requires fewer bits than actually representing the individual pels. Compression is, thereby, achieved.
Video compression algorithms using vector quantization, however, have not found much use in real time video platforms because of their complexity. Every coding block must typically be searched into the entire codebook, thereby requiring a large amount of computation time which may contribute to delays. In addition, the codebooks often require a great deal of memory. In systems where memory size is limited, allocation of memory space presents a further problem. It is desirable, therefore, to improve the implementation of vector quantization in systems where memory size is limited so that the video coder may be used in real-time applications.